package com.sx.sx1.lintcode.day717;

import java.util.*;



public class LC3686 {


    static class UndirectedGraphNode {
        int label;
        List<UndirectedGraphNode> neighbors;

        UndirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<UndirectedGraphNode>();
        }
    }


    static class Solution {
        /**
         * @param root: the root of the tree
         * @return: Maximum diameter of the N-ary Tree
         */
        public int diameter(UndirectedGraphNode root) {
            if(root ==null) return 0;
            Map<UndirectedGraphNode, Set<UndirectedGraphNode>> graph = new HashMap<>();
            buildGraph(root, graph);

            //宽度右边遍历2次，第一次最后遍历到的节点last,
            // last一定是直径的一个端点之一
            // 那么从last出发，再次宽度优先遍历，有几层，直径就是几
            Set<UndirectedGraphNode> visited = new HashSet<>();
            UndirectedGraphNode last = null;
            Queue<UndirectedGraphNode> q = new LinkedList<>();
            q.add(root);
            visited.add(root);
            while (!q.isEmpty()){
                int size = q.size();
                for (int i = 0; i <size ; i++) {
                    UndirectedGraphNode pop = q.poll();
                    Set<UndirectedGraphNode> nexts = graph.get(pop);
                    for (UndirectedGraphNode next : nexts) {
                        if(!visited.contains(next)){
                            q.add(next);
                            last = next;
                            visited.add(next);
                        }
                    }
                }
            }

            //从last出发再次BFS
            int ans =0;
            visited.clear();
            q.add(last);
            visited.add(last);
            while (!q.isEmpty()){
                ans++;
                int size = q.size();
                for (int i = 0; i <size ; i++) {
                    UndirectedGraphNode pop = q.poll();
                    Set<UndirectedGraphNode> nexts = graph.get(pop);
                    for (UndirectedGraphNode next : nexts) {
                        if(!visited.contains(next)){
                            q.add(next);
                            visited.add(next);
                        }
                    }
                }
            }

            return ans-1;
        }

        public void buildGraph(UndirectedGraphNode cur, Map<UndirectedGraphNode, Set<UndirectedGraphNode>> g) {
            //建立图
            if (cur == null) return;
            if (!g.containsKey(cur)) {
                g.put(cur, new HashSet<>());
            }

            for (UndirectedGraphNode next : cur.neighbors) {
                if (!g.containsKey(next)) {
                    g.put(next, new HashSet<>());
                }

                g.get(cur).add(next);
                g.get(next).add(cur);
                buildGraph(next, g);
            }
        }
    }

    public static void main(String[] args) {
        UndirectedGraphNode n1 = new UndirectedGraphNode(1);
        UndirectedGraphNode n2 = new UndirectedGraphNode(2);
        UndirectedGraphNode n3 = new UndirectedGraphNode(3);
        UndirectedGraphNode n4 = new UndirectedGraphNode(4);
        UndirectedGraphNode n5 = new UndirectedGraphNode(5);
        UndirectedGraphNode n6 = new UndirectedGraphNode(6);
        UndirectedGraphNode n7 = new UndirectedGraphNode(7);
        UndirectedGraphNode n8 = new UndirectedGraphNode(8);
        UndirectedGraphNode n9 = new UndirectedGraphNode(9);
        UndirectedGraphNode n10 = new UndirectedGraphNode(10);
        UndirectedGraphNode n11 = new UndirectedGraphNode(11);

        n8.neighbors.add(n10); n9.neighbors.add(n11);
        n6.neighbors.add(n8); n7.neighbors.add(n9);

        n2.neighbors.add(n6); n2.neighbors.add(n7);

        n1.neighbors.add(n2);  n1.neighbors.add(n3); n1.neighbors.add(n4);  n1.neighbors.add(n5);


        Solution obj = new Solution();
        Solutionok obj1 = new Solutionok();
        System.out.println(obj.diameter(n1));
        System.out.println(obj1.diameter(n1));

    }

    /**
     * Definition for Undirected graph.
     * class UndirectedGraphNode {
     * int label;
     * List<UndirectedGraphNode> neighbors;
     * UndirectedGraphNode(int x) {
     * label = x;
     * neighbors = new ArrayList<UndirectedGraphNode>();
     * }
     * }
     */

    static class Solutionok {
        private Set<UndirectedGraphNode> visited;
        private UndirectedGraphNode next;
        private int res;

        public Solutionok() {
            visited = new HashSet<>();
            next = null;
            res = 0;
        }

        public int diameter(UndirectedGraphNode root) {
            Map<UndirectedGraphNode, Set<UndirectedGraphNode>> graph = new HashMap<>();
            buildGraph(root, graph);
            next = root;
            dfs(next, 0, graph);
            visited.clear();
            dfs(next, 0, graph);

            return res;
        }

        private void buildGraph(UndirectedGraphNode node, Map<UndirectedGraphNode, Set<UndirectedGraphNode>> graph) {
            if (node == null) {
                return;
            }
            if (!graph.containsKey(node)) {
                graph.put(node, new HashSet<>());
            }
            for (UndirectedGraphNode neighbor : node.neighbors) {
                graph.get(node).add(neighbor);
                if (!graph.containsKey(neighbor)) {
                    graph.put(neighbor, new HashSet<>());
                }
                graph.get(neighbor).add(node);
                buildGraph(neighbor, graph);
            }
        }

        private void dfs(UndirectedGraphNode node, int d, Map<UndirectedGraphNode, Set<UndirectedGraphNode>> graph) {
            if (visited.contains(node)) {
                return;
            }
            visited.add(node);

            if (d > res) {
                res = d;
                next = node;
            }

            if (graph.containsKey(node)) {
                for (UndirectedGraphNode neighbor : graph.get(node)) {
                    dfs(neighbor, d + 1, graph);
                }
            }
        }


    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
3686 · N 叉树的直径
算法
中等
通过率
33%

题目
题解5
笔记
讨论1
排名
记录
描述
给定一棵 N 叉树的根节点 root，返回这棵树的直径长度。

N 叉树的直径指的是树中任意两个节点间的路径中 最长的路径长度，其中这条路径 不一定经过根节点。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


N 叉树的深度小于或等于 1000
节点总个数在
[

0
,

1
0
4

]
[ 0, 10
4
  ] 之间

样例
样例 1：

输入：
{1,3,2,4#2#3,5,6#4#5#6}
输出：
3
解释：
如下图红线路径
3686_1.png

样例 2：

输入：
{1,2,3,4,5#2,6,7#3#4#5#6,8#7,9#8,10#9,11#10#11}
输出：
6
解释：
如下图红线
3686_2.png

标签
相关题目

1181
二叉树的直径
简单

3663
无向树的直径
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
97/1859
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
}
控制台
历史提交

 */
